#pragma once

#include <utility>
#include "Common.hpp"

using std::endl;
using std::cout;
using std::cin;

template<class T>
class TCMalloc_PageMap1_Iterator
{
public:
	typedef TCMalloc_PageMap1_Iterator<T> Self;
	typedef std::pair<T**, T*> itrator_pair;

	void* _root;
	itrator_pair _pair;

public:
	TCMalloc_PageMap1_Iterator(void* root = nullptr, T** pair_first_Ptr = nullptr, T* pair_second_Ptr = nullptr): _root(root)
	{
		_pair.first = pair_first_Ptr;
		_pair.second = pair_second_Ptr;
	}

	itrator_pair* operator->()
	{
		return &_pair;
	}

	itrator_pair& operator*()
	{
		return _pair;
	}

	bool operator!=(const Self& self)const
	{
		return self._root != this->_root || self._pair.second != this->_pair.second;
	}
	bool operator==(const Self& self)const
	{
		return self._root == this->_root && self._pair.second == this->_pair.second;
	}
};


// Single-level array
template <typename T,int BITS>        // BITS 是页号长度    例如： BITS = 32位 - 13位(8k)
class TCMalloc_PageMap1 :protected AllocHelper
{
private:
	static const int LENGTH = 1 << BITS;   // LENGTH  指的是存储所有页号所需的数组总长度  例如: BITS=32-13 = 19  LENGHR 1<<19
	T** array_;   // 存储一级指针的数要用二级指针
public:
	typedef uintptr_t Number;
	typedef TCMalloc_PageMap1_Iterator<T> iterator;


	// explicit 禁止隐式类型转换
	explicit TCMalloc_PageMap1(void* (*allocator)(size_t))
	{
		array_ = reinterpret_cast<T**>((*allocator)(sizeof(T*) << BITS));    //指针大小 * 2^5     << BITS
		memset(array_, 0, sizeof(T*) << BITS);
	}

	explicit TCMalloc_PageMap1()
	{
		//array_ = reinterpret_cast<void**>((*allocator)(sizeof(void*) << BITS));    指针大小 * 2^5     << BITS
		// 【修改点 1】
		array_ = reinterpret_cast<T**>(SystemAlloc(SizeClass::RoundUp(sizeof(T*) << BITS) >> PAGE_SHIFT));  //  指针大小 * 2 ^ 5, 计算第一页需要的内存
		

		memset(array_, 0, sizeof(T*) << BITS);
	}


	// Return the current value for KEY. Returns NULL if not yet set,
	// or if k is out of range.
	T* get(Number k) const 
	{
		if ((k >> BITS) > 0) {
			assert(false);
		}
		return array_[k];
	}

	// REQUIRES "k" is in range "[0,2^BITS-1]".
	// REQUIRES "k" has been ensured before.
	//
	// Sets the value 'v' for key 'k'.
	void set(Number k, T* v)
	{
		array_[k] = v;
	}

	T*& operator[](Number k)
	{
		if ((k >> BITS) > 0)
		{
			assert(false);
		}
		return array_[k];
	}

	const iterator find(Number k)
	{
		if ((k >> BITS) > 0)
		{
			assert(false);
		}

		return iterator(this, array_, array_[k]);
	}

	const iterator end()
	{
		return iterator(this);
	}
};

















//// Two-level radix tree
template <typename T, int BITS>
class TCMalloc_PageMap2 
{
private:
	// Put 32 entries in the root and (2^BITS)/32 entries in each leaf.

	// 这里是分层存储页号，取页号的前5位作为第一层，6~19作为第二层存储
	static const int ROOT_BITS = 5;        // 第一层存储的页号数为 5，需要 2^5 个槽位
	static const int ROOT_LENGTH = 1 << ROOT_BITS;   // 第一层映射数组的长度 需要 2^5 个槽位 
	static const int LEAF_BITS = BITS - ROOT_BITS;   // 第二层存储的页号为出去前五位后，剩下的页号数
	static const int LEAF_LENGTH = 1 << LEAF_BITS;   // 存储剩下的页号，所需要剩下的位数
	// Leaf node
	struct Leaf 
	{
		T* values[LEAF_LENGTH];
	};

	Leaf* root_[ROOT_LENGTH];             // Pointers to 32 child nodes

	void* (*allocator_)(size_t);          // Memory allocator

public:
	typedef uintptr_t Number;   //  uintptr_t 可以保证长度与机器的指针长度一致
	typedef TCMalloc_PageMap1_Iterator<T> iterator;


	explicit TCMalloc_PageMap2(void* (*allocator)(size_t)) {
		allocator_ = allocator;
		memset(root_, 0, sizeof(root_));
	}

	explicit TCMalloc_PageMap2() {
		memset(root_, 0, sizeof(root_));   // 开辟第一层的空间

		// 将所有的空间全部进行开辟
		PreallocateMoreMemory();
	}

	// 将 start~ start + n - 1 之间的子节点的内存全部开辟
	bool Ensure(Number start, size_t n)
	{
		for (Number key = start; key <= start + n - 1;)
		{
			const Number i1 = key >> LEAF_BITS;
			// Check for overflow
			if (i1 >= ROOT_LENGTH)
				return false;
			// Make 2nd level node if necessary
			if (root_[i1] == NULL)
			{
				//Leaf* leaf = reinterpret_cast<Leaf*>((*allocator_)(sizeof(Leaf)));

				//  static 修饰,全局只有一份  sizeof(Leaf) << ROOT_BITS 
				static ObjectPool<Leaf> leafpool(sizeof(Leaf) << ROOT_BITS);   //将未来需要的全部内存，全都开辟在这个定长内存池

				Leaf* leaf = reinterpret_cast<Leaf*>(leafpool.New());

				if (leaf == NULL) return false;
				memset(leaf, 0, sizeof(*leaf));
				root_[i1] = leaf;
			}
			// Advance key past whatever is covered by this leaf node
			key = ((key >> LEAF_BITS) + 1) << LEAF_BITS;
		}
		return true;
	}
	void PreallocateMoreMemory() {
		// Allocate enough to keep track of all possible pages

		// 这里直接把所有的空间全部开辟出来  0 ~ 1<<BITS
		Ensure(0, 1 << BITS);
	}



	void* get(Number k) const 
	{
		const Number i1 = k >> LEAF_BITS;
		const Number i2 = k & (LEAF_LENGTH - 1);
		if ((k >> BITS) > 0 || root_[i1] == NULL) {
			return NULL;
		}
		return root_[i1]->values[i2];
	}

	void set(Number k, void* v) 
	{
		const Number i1 = k >> LEAF_BITS;
		const Number i2 = k & (LEAF_LENGTH - 1);   // 保留第二层剩下的比特位
		ASSERT(i1 < ROOT_LENGTH);
		root_[i1]->values[i2] = v;
	}

	T*& operator[](Number k)
	{
		const Number i1 = k >> LEAF_BITS;
		const Number i2 = k & (LEAF_LENGTH - 1);
		if ((k >> BITS) > 0 || root_[i1] == nullptr) 
		{
			assert(false);
		}
		return root_[i1]->values[i2];
	}

	const iterator find(Number k)
	{
		const Number i1 = k >> LEAF_BITS;
		const Number i2 = k & (LEAF_LENGTH - 1);
		if ((k >> BITS) > 0 || root_[i1] == nullptr)
		{
			assert(false);
		}
		
		root_[i1]->values[i2];
		

		return iterator(this , nullptr, root_[i1]->values[i2]);
	}

	const iterator end()
	{
		return iterator(this);
	}

};



//
//
//// 三层用于 64位
//// Three-level radix tree
template <typename T, int BITS>
class TCMalloc_PageMap3 
{
private:
	// How many bits should we consume at each interior level
	static const int INTERIOR_BITS = (BITS + 2) / 3; // Round-up
	static const int INTERIOR_LENGTH = 1 << INTERIOR_BITS;
	// How many bits should we consume at leaf level
	static const int LEAF_BITS = BITS - 2 * INTERIOR_BITS;
	static const int LEAF_LENGTH = 1 << LEAF_BITS;
	// Interior node
	struct Node 
	{
		Node* ptrs[INTERIOR_LENGTH];
	};
	// Leaf node
	struct Leaf 
	{
		T* values[LEAF_LENGTH];
	};
	Node* root_;                          // Root of radix tree
	void* (*allocator_)(size_t);          // Memory allocator

	Node* NewNode() 
	{
		static ObjectPool<Node> Nodepool(sizeof Node * 5);  // 每次5个五个申请

		Node* result = (Nodepool.New());

		if (result != NULL) 
		{
			memset(result, 0, sizeof(Node));
		}
		return result;
	}

public:
	typedef uintptr_t Number;
	typedef TCMalloc_PageMap1_Iterator<T> iterator;


	explicit TCMalloc_PageMap3(void* (*allocator)(size_t)) 
	{
		allocator_ = allocator;
		root_ = NewNode();
	}

	explicit TCMalloc_PageMap3()
	{
		root_ = NewNode();
	}

	bool Ensure(Number start, size_t n) 
	{
		for (Number key = start; key <= start + n - 1;) {
			const Number i1 = key >> (LEAF_BITS + INTERIOR_BITS);
			const Number i2 = (key >> LEAF_BITS) & (INTERIOR_LENGTH - 1);
			// Check for overflow
			if (i1 >= INTERIOR_LENGTH || i2 >= INTERIOR_LENGTH)
				return false;
			// Make 2nd level node if necessary
			if (root_->ptrs[i1] == NULL) 
			{
				Node* n = NewNode();
				if (n == NULL) return false;
				root_->ptrs[i1] = n;
			}
			// Make leaf node if necessary
			if (root_->ptrs[i1]->ptrs[i2] == NULL) 
			{
				//Leaf* leaf = reinterpret_cast<Leaf*>((*allocator_)(sizeof(Leaf))); 
				static ObjectPool<Leaf> leafpool(sizeof Leaf * 10);  // 叶子每次10个每次10个

				Leaf* leaf = reinterpret_cast<Leaf*>(leafpool.New());

				if (leaf == NULL) return false;
				memset(leaf, 0, sizeof(*leaf));
				root_->ptrs[i1]->ptrs[i2] = reinterpret_cast<Node*>(leaf);
			}
			// Advance key past whatever is covered by this leaf node
			key = ((key >> LEAF_BITS) + 1) << LEAF_BITS;
		}
		return true;
	}

	void PreallocateMoreMemory() 
	{

	}

	void* get(Number k) const 
	{
		const Number i1 = k >> (LEAF_BITS + INTERIOR_BITS);
		const Number i2 = (k >> LEAF_BITS) & (INTERIOR_LENGTH - 1);
		const Number i3 = k & (LEAF_LENGTH - 1);
		if ((k >> BITS) > 0 || root_->ptrs[i1] == NULL || root_->ptrs[i1]->ptrs[i2] == NULL)
		{
			return NULL;
		}
		return reinterpret_cast<Leaf*>(root_->ptrs[i1]->ptrs[i2])->values[i3];
	}

	void set(Number k, T* v)
	{
		assert(k >> BITS == 0);
		const Number i1 = k >> (LEAF_BITS + INTERIOR_BITS);
		const Number i2 = (k >> LEAF_BITS) & (INTERIOR_LENGTH - 1);
		const Number i3 = k & (LEAF_LENGTH - 1);

		Ensure(k, 1);

		reinterpret_cast<Leaf*>(root_->ptrs[i1]->ptrs[i2])->values[i3] = v;
	}

	T*& operator[](Number k)
	{
		assert(k >> BITS == 0);
		const Number i1 = k >> (LEAF_BITS + INTERIOR_BITS);
		const Number i2 = (k >> LEAF_BITS) & (INTERIOR_LENGTH - 1);
		const Number i3 = k & (LEAF_LENGTH - 1);

		Ensure(k, 1);

		return reinterpret_cast<Leaf*>(root_->ptrs[i1]->ptrs[i2])->values[i3];
	}

	const iterator find(Number k)
	{

		assert(k >> BITS == 0);
		const Number i1 = k >> (LEAF_BITS + INTERIOR_BITS);
		const Number i2 = (k >> LEAF_BITS) & (INTERIOR_LENGTH - 1);
		const Number i3 = k & (LEAF_LENGTH - 1);

		Ensure(k, 1);

		return iterator(this, nullptr, reinterpret_cast<Leaf*>(root_->ptrs[i1]->ptrs[i2])->values[i3]);
	}

	const iterator end()
	{
		return iterator(this);
	}
};
